
				GAZE LA VILE

	Proprietarii a n (2<=n<=50) vile din zona rezidentiala a municipiului Medias au
solicitat Regiei ROMGAZ instalarea de cisterne cu metan. ROMGAZ dispune de cisterne care
asigura consumul pentru k vile pe o perioada acceptabila de timp ( k este divizor al lui
n, 2<=k<=n ).
	Pentru a i se asigura securitatea, fiecare cisterna este instalata langa o vila.
Costul conectarii unei vile este egal cu lungimea conductei pana la cisterna sau pana la
o alta vila conectata.
	Sa se determine grupe de k vile astfel incat costul conectarii tuturor vilelor
sa fie minim.

	OBSERVATII: Exista vile intre care nu se poate instala conducta de conectare. Distanta
intre acestea nu este specificata. Costul conectarii vilei de langa cisterna este nul.

	DATE DE INTRARE

	Fisierul "gaze.in" contine pe prima linie
n k            - numarul total de vile si numarul de vile care pot fi conectate la o cisterna,
urmate de un numar de linii de forma :
i j1 d1 j2 d2 .. jm dm    - vila i se poate conecta la una din vilele j1,j2,..,jm si se afla,
respectiv, la distanta d1,d2,..,dm de acestea (i<j1,i<j2,..,i<jm). Distantele d1,..,dm sunt
numere naturale (1<=d1,..,dm<=50).

	DATELE DE IESIRE

	Fisierul de iesire "gaze.out" contine pe prima linie
t               - costul total al conectarii celor n vile, urmat de (n div k) linii de forma
j1 j2 .. jk c   - vilele j1 j2 .. jk sunt conectate la aceeasi cisterna, iar costul conectarii
		  lor este c
sau,
daca cele n vile nu pot fi conectate cate k :
0

EXEMPLe:

GAZE.IN				GAZE.IN
9 3				4 2
1 6 1 8 3 9 5			1 2 1 3 1 4 1
2 4 4 6 2
3 5 3 7 3			GAZE.OUT
4 9 6				0
5 7 3

GAZE.OUT
20
2 4 6 6
1 8 9 8
3 5 7 6	